skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Anastos, M."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; (, Journal of combinatorial theory)
    We discuss the length {\red $$L_{c,n}$$} of the longest cycle in a sparse random graph {\red $$G_{n,p},$$ $p=c/n$,} $$c$$ constant. We show that for large $$c$$ there exists a function $f(c)$ such that $$L_{c,n}/n\to f(c)$$ a.s. The function $$f(c)=1-\sum_{k=1}^\infty p_k(c)e^{-kc}$$ where $$p_k{\red (c)}$$ is a polynomial in $$c$$. We are only able to explicitly give the values $$p_1,p_2$$, although we could in principle compute any $$p_k$$. We see immediately that the length of the longest path is also asymptotic to $f(c)n$ w.h.p. 
    more » « less
    Full Text Available 
  2. ; (, Random structures algorithms)
    On the connectivity of proper colorings of random graphs and hypergraphs 
    more » « less
    Accepted Manuscript Full Text Available
  3. ; ; (, The electronic journal of combinatorics)
    Let $$\Omega_q$$ denote the set of proper $[q]$-colorings of the random graph $$G_{n,m}, m=dn/2$$ and let $$H_q$$ be the graph with vertex set $$\Omega_q$$ and an edge $$\set{\s,\t}$$ where $$\s,\t$$ are mappings $$[n]\to[q]$$ iff $$h(\s,\t)=1$$. Here $$h(\s,\t)$$ is the Hamming distance $$|\set{v\in [n]:\s(v)\neq\t(v)}|$$. We show that w.h.p. $$H_q$$ contains a single giant component containing almost all colorings in $$\Omega_q$$ if $$d$$ is sufficiently large and $$q\geq \frac{cd}{\log d}$$ for a constant $c>3/2$. 
    more » « less
    Accepted Manuscript Full Text Available